package cxydmmszl.chapter01.t007;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 生成窗口最大值数组
 *      有一个整型数组 arr 和一个大小为 w 的窗口从数组的左边滑到最右边，窗口每次向右边滑一个位置。
 * CD15
 *
 * @author habitplus
 * @since 2021-08-23 22:49
 */
public class Main {
    public int[] genWindowMaxArr(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }

        // 双端队列
        Deque<Integer> qmax = new LinkedList<>();
        int[]  res = new int[arr.length - w + 1];
        int k = 0;

        for (int i = 0; i < arr.length; i++) {
            // 维持一个递减的双端队列，
            // 所有小于或等于 当前数 的以前的值都退出队列
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
                qmax.pollLast();
            }

            qmax.offerLast(i);

            // 当前队列中最大的队首元素就是要删除范围里的左边界上的数
            if (qmax.peekFirst() == i - w) {
                qmax.pollFirst();
            }

            if (i >= w - 1) {
                res[k++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        Main test = new Main();
        int[] ans = test.genWindowMaxArr(arr, w);
        StringBuilder sb = new StringBuilder();
        for (int i : ans) {
            sb.append(i).append(" ");
        }
        System.out.println(sb.toString());
    }
}
